/**
 * @ClassName MatrixChain
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/2 9:06
 */
public class MatrixChain {


    /**
     * 矩阵连乘算法
     * @param p 保存了矩阵的行数和列数, 大小为实际矩阵数 + 1 <br>例子: A1: 30 * 35, A2: 35 * 15, 那么p=[30, 35, 15]
     * @param n 有多少个矩阵
     * @param m m[i][j]表示从矩阵i到矩阵j做乘法的最少运算次数
     * @param s s[i][j]表示矩阵i到矩阵j的最少次数的乘法的分隔位置
     *          <br>例子:A1 * A2 * A3最少运算次数的分发为:(A1 * A2) * A3, 那么s[1][3] = 2
     */
    public static void matrixChain(int[] p, int n, int[][] m, int[][] s) {
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }
        // i代表有多少个矩阵相乘
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                // 从A[i]乘到A[j]
                int j = i + r - 1;
                m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
                s[i][j] = i;
                for (int k = i + 1; k < j; k++) {
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
    }

}
